class Solution {
    public int maxProfit(int[] prices) {
        int[] temp = new int[prices.length + 1];
        System.arraycopy(prices, 0, temp, 1, prices.length);
        temp[0] = 0;
        prices = temp;
        int[][][] f = new int[2][2][2];
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                for (int k = 0; k < 2; k++) {
                    f[i][j][k] = -10000000;
                }
            }
        }
        f[0][0][0] = 0;
        for (int i = 1; i < prices.length; i++) {
            for (int j = 0; j < 2; j++) {
                for (int k = 0; k < 2; k++) {
                    int tmp = (i - 1)&1;
                    if (j == 1 && k == 0) {
                        f[i&1][1][0] = Math.max(f[i&1][1][0], f[tmp][0][0] - prices[i]);
                    } else if (j == 0 && k == 1) {
                        f[i&1][0][1] = Math.max(f[i&1][0][1], f[tmp][1][0] + prices[i]);
                    }
                    f[i&1][j][0] = Math.max(f[i&1][j][0], f[tmp][j][k]);
                }
            }
        }
        int profit = 0;
        for (int k = 0; k < 2; k++) {
            profit = Math.max(profit, f[(prices.length-1)&1][0][k]);
        }
        return profit;
    }
}
/**
f[i][j][k] 
买入：j == 1 && k == 0: f[i][1][0] = f[i-1][0][0] - prices[i]
卖出：j == 0 && k == 1: f[i][0][1] = f[i-1][1][0] + prices[i]
观望：f[i][j][0] = f[i-1][j][k]
求：f[n][0][k]
 */
